package com.berchen.数据结构.递归;

/**
 * 八皇后问题
 * 通过递归回溯来解决
 * 棋子不能再同一行 同一列 同一斜线
 *
 * 我们用一个一维数组 来解决  因为一行只能放一个棋子 所以 一个索引就是一行
 */
public class EightQueens {

    private int size;
    private int[] arr;
    private int count=0;

    public EightQueens(int size) {
        this.size = size;
        arr=new int[size];
    }

    public int getCount() {
        return count;
    }

    /**
     * 摆放棋子
     * @param n 摆放的第几个皇后 第一个皇后  n=0  第二个皇后 n=1 因为这里是用的索引
     */
    public void place(int n){

        if(n==size){    // 8 == 8  这时候这一轮摆放已经摆好了
            print();
            return;
        }
        // 这里j表示第几列 n表示第几个皇后（棋子、行）
        for(int j =0;j<size;j++){
            // 将这个皇后放到这一行的第i列 进行遍历 每一列
            arr[n]=j;
            if(isLegitimate(n)){    // 判断棋子是否合法
                place(n+1); // 摆放下一个棋子   进入到下一行
            }
            // 棋子不合法 就继续遍历这一行的下一列
        }
    }

    /**
     * 打印
     */
    public void print(){
        count++;
        for(int i =0;i<size;i++){
            System.out.printf("%d\t",arr[i]);
        }
        System.out.println();
    }

    /**
     * 判断该棋子是否合法
     * @param n 第几个皇后 第一个皇后  n=0  第二个皇后 n=1 因为这里是用的索引
     * @return
     */
    public boolean isLegitimate(int n){

        for(int i =0;i<n;i++){
            // 不合法
            // arr[i]==arr[n] 用来判断是否在同一列上面
            // Math.abs(n-i)==Math.abs(arr[n]-arr[i]) 用来判断是否在同一斜线上
            if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }

}
